\section{An Algorithm to Tune Energy Efficiency}\label{sec:tuning-ee}
%
%\TODO{[RV] Since I changed a lot of notation, someone should re-read this section and make the notation consistent.}
We can use the model to give an algorithm for the problem of maximimizing energy-efficiency subject to constraints on quality-of-service and a power bound, formalized as follows.
Let $W$ be the set of programs we wish to execute on the multicore processor.
(Assume, as in our experimental setup, that each program $w \in W$ corresponds, for instance, to one of the SPEC 2006 benchmarks.)
Let $TP$ be the overall throughput (work per unit time) of all the cores.
The energy-efficiency of executing $W$ on our multicore processor is $TP / \PowerMC$, where $\PowerMC$   comes from our model;
thus, energy-efficiency has units of work per unit energy.
The problem we wish to consider is how to maximize energy-efficiency by assigning each core an appropriate frequency, subject to the quality-of-service and power bound constraints.
A quality-of-service constraint says that the effective speed $Ef(w)$ of running $w$ exceeds the user's requested speed $Rf(w)$.
A power bound constraint says that $\PowerMC$ must never exceed some fixed power limit, $PB$.
The formal optimization problem becomes,
\begin{eqnarray}
    & \max \frac{TP}{P_{MC}} \label{eq:problem}\\
  \mbox{s.t.}
    & \PowerMC(F) \le PB \label{eq:constraint1}\\
    & \forall w \in W: Ef(w) \ge Rf(w) \label{eq:constraint2} .
\end{eqnarray}

\RefAlgorithm{algo:energyefficient} presents an algorithm for selecting the frequency settings for the formal optimization problem above.
The inputs to the algorithm are the power budget, $PB$, the user required speed $F_r$ and the simplified power model which has $K$ pieces and the coefficients given by an array $M$.
The output is the core speed setting that meets the power and speed constraints, or \textbf{null} if there is no such setting.

The algorithm works as follows.
If the given speed requirement needs more power than the budget, then \textbf{null} will be returned (line 1 and 2).
Otherwise, we first get the Pareto optimal point $CurF$, which has the same power consumption as required speed $F_r$ but the maximum average speed $MaxF$ (line 3 and 4).
Then we select the piece whose frequency is faster than the required one (line 5).

Based on our simplified model, \refeq{eq:problem} can be simplified as $\frac{MaxF}{a_{s,0}+a_{s,1}\times MaxF}=\frac{1}{\frac{a_{s,0}}{MaxF}+a_{s,1}}$, so if $(a_{s,0}\le 0)$, lower speed will achieve higher energy-efficiency.
The minimum speed can meet the requirement is $MaxF$, so $CurF=[MaxF,...,MaxF]$ is returned (line 6 and 7).
If $(a_{s,0}> 0)$, the faster speed will achieve higher energy efficiency, so we compare all the speeds faster than the required one and meeting the power budget, then we return the best result (line 8$\sim$18).

\begin{algorithm}
\DontPrintSemicolon % Some LaTeX compilers require you to use \dontprintsemicolon instead
\KwIn{Power Budget $PB$, Speed Requirement $F_r$ from user, $K$ pieces Simplified Power Model $M[K]$}
\KwOut{Energy Efficient Speed Distribution $F_{ee}$}
\If {$P_{MC}(F_r)> PB$} {
    \Return {null } \;
}
$MaxF=max(F_r)$\;
$CurF=[MaxF,...,MaxF]$\;
Select the $s$th piecewise model  whose speed range meets $f_{p_{s-1}} \le MaxF <f_{p_{s}}$.\;
\If {$(a_{s,0}\le 0)$} {
    \Return {$CurF$}\;
}
\If {$(a_{s,0}> 0)$} {
    $CurEE=\frac{Max(CurF)}{P_{MC}(CurF)}$\;
    $CurP=P_{MC}(CurF)$\;
    \For{$i \gets s $ \textbf{to} $K$}{
        $TmpF=[f_{p_{i}},...,f_{p_{i}}]$\;
        $TmpP=P_{MC}(TmpF)$\;
        $TmpEE=\frac{f_{p_{i}}}{P_{MC}(TmpF)}$\;
        \If {$((TmpEE>CurEE) \&\& (TmpP \le PB)) $}{
            $CurF=TmpF$\;
            $CurEE=TmpEE$\;
        }
    }
}
\Return{$CurF$}\;
\caption{Select the energy efficient speed distribution}
\label{algo:energyefficient}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
